The Map Interface

The JavaTM Tutorial

| Start of Tutorial > Start of Trail > Start of Lesson | Search Feedback Form

Trail: Collections
Lesson: Interfaces

## The Map Interface

> A `Map` is an object that maps keys to values. A map cannot contain duplicate keys: Each key can map to at most one value. The `Map` interface follows.

> >     public interface Map {

> >         //Basic operations
> >         V put(K key, V value);
> >         V get(Object key);
> >         V remove(Object key);
> >         boolean containsKey(Object key);
> >         boolean containsValue(Object value);
> >         int size();
> >         boolean isEmpty();

> >         //Bulk operations
> >         void putAll(Map<? extends K,? extends V> t);
> >         void clear();

> >         // Collection Views
> >         public Set<K> keySet();
> >         public Collection<V> values();
> >         public Set<Map.Entry<K,V>> entrySet();

> >         // Interface for entrySet elements
> >         public interface Entry {
> >             K getKey();
> >             V getValue();
> >             V setValue(V value);
> >         }
> >     }

> The Java platform contains three general-purpose `Map` implementations: `HashMap`, `TreeMap`, and `LinkedHashMap`. Their behavior and performance are precisely analogous to `HashSet`, `TreeSet`, and `LinkedHashSet`, as described in The Set Interface section. Also, `Hashtable` was retrofitted to implement `Map`.

### Comparison to Hashtable

> If you've used `Hashtable`, you're already familiar with the general basics of `Map`. (Of course `Map` is an interface, while `Hashtable` is a concrete implementation.) The following are the major differences:
> - `Map` provides `Collection` views instead of direct support for iteration via `Enumeration` objects. `Collection` views greatly enhance the expressiveness of the interface, as discussed later in this section.
> - `Map` allows you to iterate over keys, values, or key-value pairs; `Hashtable` does not provide the third option.
> - `Map` provides a safe way to remove entries in the midst of iteration; `Hashtable` did not.
> Finally, `Map` fixes a minor deficiency in the `Hashtable` interface. `Hashtable` has a method called `contains`, which returns `true` if the `Hashtable` contains a given value. Given its name, you'd expect this method to return `true` if the `Hashtable` contained a given key, because the key is the primary access mechanism for a `Hashtable`. The `Map` interface eliminates this source of confusion by renaming the method `containsValue`. Also, this improves the interface's consistency — `containsValue` parallels `containsKey`.

### Map Interface Basic Operations

> The basic operations of `Map` (`put`, `get`, `containsKey`, `containsValue`, `size`, and `isEmpty`) behave exactly like their counterparts in `Hashtable`. The following `program generates a frequency table` of the words found in its argument list. The frequency table maps each word to the number of times it occurs in the argument list.

> >     import java.util.*;
> >     public class Freq {
> >         public static void main(String args[]) {
> >             Map<String, Integer>	 m =
> >                 new HashMap<String, Integer>();

> >             // Initialize frequency table from command line
> >             for (String a : args) {
> >                 Integer freq = m.get(a);
> >                 m.put(a, (freq == null ? 1 : freq + 1));
> >             }
> >             System.out.println(m.size() + " distinct words:");
> >             System.out.println(m);
> >         }
> >     }

> The only tricky thing about this program is the second argument of the `put` statement. That argument is a conditional expression that has the effect of setting the frequency to one if the word has never been seen before or one more than its current value if the word has already been seen. Try running this program with the command:

> >     java Freq if it is to be it is up to me to delegate

> The program yields the following output.

> >     8 distinct words:
> >     {to=3, delegate=1, be=1, it=2, up=1, if=1, me=1, is=2}

> Suppose you'd prefer to see the frequency table in alphabetical order. All you have to do is change the implementation type of the `Map` from `HashMap` to `TreeMap`. Making this four-character change causes the program to generate the following output from the same command line.

> >     8 distinct words:
> >     {be=1, delegate=1, if=1, is=2, it=2, me=1, to=3, up=1}

> Similarly, you could make the program print the frequency table in the order the words first appear on the command line simply by changing the implementation type of the map to `LinkedHashMap`. Doing so results in the following output.

> >     8 distinct words:
> >     {if=1, it=2, is=2, to=3, be=1, up=1, me=1, delegate=1}

> This flexibility provides a potent illustration of the power of an interface-based framework.

> Like the `Set`and `List`interfaces, `Map` strengthens the requirements on the `equals` and `hashCode` methods so that two `Map` objects can be compared for logical equality without regard to their implementation types. Two `Map` instances are equal if they represent the same key-value mappings.

> By convention, all `Map` implementations provide constructors that take a `Map` object and initialize the new `Map` to contain all the key-value mappings in the specified `Map`. This standard `Map` conversion constructor is entirely analogous to the standard `Collection` constructor: It allows the caller to create a `Map` of a desired implementation type that initially contains all of the mappings in another `Map`, regardless of the other `Map`'s implementation type. For example, suppose you have a `Map`, named `m`. The following one-liner creates a new `HashMap` initially containing all of the same key-value mappings as `m`.

> >     Map<K, V> copy = new HashMap<K, V>(m);

### Map Interface Bulk Operations

> The `clear` operation does exactly what you would think it could do: it removes all the mappings from the `Map`. The `putAll` operation is the `Map` analogue of the `Collection` interface's `addAll` operation. In addition to its obvious use of dumping one `Map` into another, it has a second, more subtle use. Suppose a `Map` is used to represent a collection of attribute-value pairs; the `putAll` operation, in combination with the `Map` conversion constructor, provides a neat way to implement attribute map creation with default values. The following is a static factory method that demonstrates this technique.

> >     static <K, V> Map<K, V> newAttributeMap(
> >             Map<K, V>defaults, Map<K, V> overrides) {
> >         Map<K, V> result = new HashMap<K, V>(defaults);
> >         result.putAll(overrides);
> >         return result;
> >     }

### Collection Views

> The `Collection` view methods allow a `Map` to be viewed as a `Collection` in these three ways:
> - `keySet` — the `Set` of keys contained in the `Map`.
> - `values` — The `Collection` of values contained in the `Map`. This `Collection` is not a `Set`, because multiple keys can map to the same value.
> - `entrySet` — the `Set` of key-value pairs contained in the `Map`. The `Map` interface provides a small nested interface called `Map.Entry`, the type of the elements in this `Set`.
> The `Collection` views provide the only means to iterate over a `Map`. This example illustrates the standard idiom for iterating over the keys in a `Map` with a `for-each` construct:

> >     for (KeyType key : m.keySet())
> >         System.out.println(key);

> and with an `iterator`:

> >     //Filter a map based on some property of its keys.
> >     for (Iterator<Type> i=m.keySet().iterator(); i.hasNext(); )
> >         if (i.next().isBogus())
> >             i.remove();

> The idiom for iterating over values is analogous. Following is the idiom for iterating over key-value pairs.

> >     for (Map.Entry<KeyType, ValType> e : m.entrySet())
> >         System.out.println(e.getKey() + ": " + e.getValue());

> At first, many people worry that these idioms may be slow because the `Map` has to create a new `Collection` instance each time a `Collection` view operation is called. Rest easy: There's no reason that a `Map` cannot always return the same object each time it is asked for a given `Collection` view. This is precisely what all the `Map` implementations in `java.util` do.

> With all three `Collection` views, calling an `Iterator`'s `remove` operation removes the associated entry from the backing `Map`, assuming that the backing `Map` supports element removal to begin with. This is illustrated by the preceding filtering idiom.

> With the `entrySet` view, it is also possible to change the value associated with a key by calling a `Map.Entry`'s `setValue` method during iteration (again, assuming the `Map` supports value modification to begin with). Note that these are the only safe ways to modify a `Map` during iteration; the behavior is unspecified if the underlying `Map` is modified in any other way while the iteration is in progress.

> The `Collection` views support element removal in all its many forms — `remove`, `removeAll`, `retainAll`, and `clear` operations, as well as the `Iterator.remove` operation. (Yet again, this assumes that the backing `Map` supports element removal.)

> The `Collection` views do not support element addition under any circumstances. It would make no sense for the `keySet` and `values` views, and it's unnecessary for the `entrySet` view, because the backing `Map`'s `put` and `putAll` methods provide the same functionality.

### Fancy Uses of Collection Views: Map Algebra

> When applied to the `Collection` views, bulk operations (`containsAll`, `removeAll`, and `retainAll`) are surprisingly potent tools. For starters, suppose you want to know whether one `Map` is a submap of another — that is, whether the first `Map` contains all the key-value mappings in the second. The following idiom does the trick.

> >     if (m1.entrySet().containsAll(m2.entrySet())) {
> >     	...
> >     }

> Along similar lines, suppose you want to know whether two `Map` objects contain mappings for all the same keys.

> >     if (m1.keySet().equals(m2.keySet())) {
> >     	...
> >     }

> Suppose you have a `Map` that represents a collection of attribute-value pairs, and two `Set`s representing required attributes and permissible attributes. (The permissible attributes include the required attributes.) The following snippet determines whether the attribute map conforms to these constraints and prints a detailed error message if it doesn't.

> >     static <K, V> boolean validate(Map<K, V> attrMap,
> >             Set<K> requiredAttrs, Set<K>permittedAttrs) {
> >         boolean valid = true;
> >         Set<K> attrs = attrMap.keySet();
> >         if(!attrs.containsAll(requiredAttrs)) {
> >             Set<K> missing = new HashSet<K>(requiredAttrs);
> >             missing.removeAll(attrs);
> >             System.out.println("Missing attributes: " + missing);
> >             valid = false;
> >         }
> >         if (!permittedAttrs.containsAll(attrs)) {
> >             Set<K> illegal = new HashSet<K>(attrs);
> >             illegal.removeAll(permittedAttrs);
> >             System.out.println("Illegal attributes: " + illegal);
> >             valid = false;
> >         }
> >         return valid;
> >     }

> Suppose you want to know all the keys common to two `Map` objects.

> >     Set<KeyType>commonKeys = new HashSet<KeyType>(m1.keySet());
> >     commonKeys.retainAll(m2.keySet);

> A similar idiom gets you the common values.

> All the idioms presented thus far have been nondestructive; that is, they don't modify the backing `Map`. Here are a few that do. Suppose you want to remove all the key-value pairs that one `Map` has in common with another.

> >     m1.entrySet().removeAll(m2.entrySet());

> Suppose you want to remove from one `Map` all the keys that have mappings in another.

> >     m1.keySet().removeAll(m2.keySet());

> What happens when you start mixing keys and values in the same bulk operation? Suppose you have a `Map`, `managers`, that maps each employee in a company to the employee's manager. We'll be deliberately vague about the types of the key and the value objects. It doesn't matter, as long as they're the same. Now suppose you want to know who all the "individual contributors" (or nonmanagers) are. The following snippet tells you exactly what you want to know.

> >     Set<Employee> individualContributors =
> >         new HashSet<Employee>(managers.keySet());
> >     individualContributors.removeAll(managers.values());

> Suppose you want to fire all the employees who report directly to some manager, Simon.

> >     Employee simon = ... ;
> >     managers.values().removeAll(Collections.singleton(simon));

> Note that this idiom makes use of `Collections.singleton`, a static factory method that returns an immutable `Set` with the single, specified element.

> Once you've done this, you may have a bunch of employees whose managers no longer work for the company (if any of Simon's direct-reports were themselves managers). The following code will tell you all the employees whose manager no longer works for the company.

> >     Map<Employee, Employee> m =
> >         new HashMap<Employee, Employee>(managers);
> >     m.values().removeAll(managers.keySet());
> >     Set<Employee> slackers = m.keySet();

> This example is a bit tricky. First, it makes a temporary copy of the `Map`, and it removes from the temporary copy all entries whose (manager) value is a key in the original `Map`. Remember that the original `Map` has an entry for each employee. Thus, the remaining entries in the temporary `Map` comprise all the entries from the original `Map` whose (manager) values are no longer employees. The keys in the temporary copy, then, represent precisely the employees that we're looking for.

> There are many more idioms like the ones contained in this section, but it would be impractical and tedious to list them all. Once you get the hang of it, it's not that difficult to come up with the right one when you need it.

### Multimaps

> A multimap is like a `Map` but it can map each key to multiple values. The Java Collections Framework doesn't include an interface for multimaps because they aren't used all that commonly. It's a fairly simple matter touse a `Map` whose values are `List` instances as a multimap. This technique is demonstrated in the next code example, which reads a wordlist containing one word per line (all lowercase) and prints out all the anagram groups that meet a size criterion. An anagram group is a bunch of words, all of which contain exactly the same letters but in a different order. The program takes two arguments on the command line: (1) the name of the dictionary file and (2) the minimum size of anagram group to print out. Anagram groups containing fewer words than the specified minimum are not printed.

> There is a standard trick for finding anagram groups: for each word in the dictionary, alphabetize the letters in the word (that is, reorder the word's letters into alphabetical order) and put an entry into a multimap, mapping the alphabetized word to the original word. For example, the word bad causes an entry mapping abd into bad to be put into the multimap. A moment's reflection will show that all the words to which any given key maps form an anagram group. It's a simple matter to iterate over the keys in the multimap, printing out each anagram group that meets the size constraint.

> `The following program` is a straightforward implementation of this technique. The only tricky part is the `alphabetize` method, which returns a string containing the same characters as its argument in alphabetical order. This routine, which has nothing to do with the Java Collections Framework, implements a slick bucket sort. It assumes that the word being alphabetized consists entirely of lowercase alphabetic characters.

> >     import java.util.*;
> >     import java.io.*;

> >     public class Anagrams {
> >         public static void main(String[] args) {
> >             int minGroupSize = Integer.parseInt(args[1]);

> >             //Read words from file and put into a simulated multimap
> >             Map<String, List<String>> m = new HashMap<String, List<String>>();
> >             try {
> >             		Scanner s = new Scanner(new File(args[0]));
> >                 String word;
> >                 while(s.hasNext()) {
> >                     String alpha = alphabetize(word = s.next());
> >                     List<String> l = m.get(alpha);
> >                     if (l==null)
> >                         m.put(alpha, l=new ArrayList<String>());
> >                     l.add(word);
> >                 }
> >             } catch(IOException e) {
> >                 System.err.println(e);
> >                 System.exit(1);
> >             }

> >             //Print all permutation groups above size threshold
> >             for (List<String> l : m.values()) {
> >                 if (l.size() >= minGroupSize)
> >                     System.out.println(l.size() + ": " + l);
> >             }
> >         }

> >         private static String alphabetize(String s) {
> >             int count[] = new int[256];
> >             int len = s.length();
> >             for (int i=0; i<len; i++)
> >                 count[s.charAt(i)]++;
> >             StringBuffer result = new StringBuffer(len);
> >             for (char c='a'; c<='z'; c++)
> >                 for (int i=0; i<count[c]; i++)
> >                     result.append(c);
> >             return result.toString();
> >         }
> >     }

> Running this program on a 173,000-word dictionary file takes about four seconds on a 1.8 GHz Pentium 4. With a minimum anagram group size of eight, it produces the following output.

> >     9: [estrin, inerts, insert, inters, niters, nitres, sinter,
> >          triens, trines]
> >     8: [lapse, leaps, pales, peals, pleas, salep, sepal, spale]
> >     8: [aspers, parses, passer, prases, repass, spares, sparse,
> >          spears]
> >     10: [least, setal, slate, stale, steal, stela, taels, tales,
> >           teals, tesla]
> >     8: [enters, nester, renest, rentes, resent, tenser, ternes,
> >          treens]
> >     8: [arles, earls, lares, laser, lears, rales, reals, seral]
> >     8: [earings, erasing, gainers, reagins, regains, reginas,
> >          searing, seringa]
> >     8: [peris, piers, pries, prise, ripes, speir, spier, spire]
> >     12: [apers, apres, asper, pares, parse, pears, prase, presa,
> >           rapes, reaps, spare, spear]
> >     11: [alerts, alters, artels, estral, laster, ratels, salter,
> >           slater, staler, stelar, talers]
> >     9: [capers, crapes, escarp, pacers, parsec, recaps, scrape,
> >          secpar, spacer]
> >     9: [palest, palets, pastel, petals, plates, pleats, septal,
> >          staple, tepals]
> >     9: [anestri, antsier, nastier, ratines, retains, retinas,
> >          retsina, stainer, stearin]
> >     8: [ates, east, eats, etas, sate, seat, seta, teas]
> >     8: [carets, cartes, caster, caters, crates, reacts, recast,
> >          traces]

> Many of these words seem a bit bogus, but that's not the program's fault; they're in the dictionary file. Here's the `dictionary file` we used. It is derived from the Public Domain ENABLE benchmark reference word list, at http://personal.riverusers.com/~thegrendel/

| Start of Tutorial > Start of Trail > Start of Lesson | Search Feedback Form

Copyright 1995-2005 Sun Microsystems, Inc. All rights reserved.